package com.cheng.algorithm.recursion;

import static sun.misc.Version.print;

/**
 * @User Administrator
 * @Classname QueenEight
 * @Project Data-structure-and-algorithm
 * @Description 八皇后问题算法思路分析：
 * 1、第一个皇后先放第一行第一列
 * 2、第二个皇后放在第二行第一列、然后判断是否OK，如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
 * 3、继续第三个皇后放第三行，还是第一列、第二列.....直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
 * 4、当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
 * 5、然后回头继续第一个皇后放第一行第二列，后面继续循环执行1,2,3,4的步骤，从而的得到放在第二列的全部正确解，
 * 6、直到第一个皇后放到了第一行的最后一列
 * @Author wpcheng
 * @Create 2021-07-29-10:53
 * @Version 1.0
 */
public class QueenEight {
    //max 皇后的数量
    int max = 8;
    static int count = 0;
    //定义一维数组array，保存皇后放置位置的结果，比如 arr = {0,4,,7,5,2,6,1,3}
    //其中数组下标+1为行号，例如：0表示第一行第一列，4表示第二行第4列，依次类推就可以表示皇后放置的位置
    int[] array = new int[max];

    public static void main(String[] args) {
        QueenEight queenEight = new QueenEight();
        queenEight.check(0);
        System.out.printf("一共有%d种解法",count);

    }
    //编写方法，放置第n个皇后
    private void check(int n){
        if (n == max){ //当 n=8时，第8个皇后已经放置完，因为n下标为0开始，为0,1,2,3,4,5,6,7
            printQueen();
            return;
        }
        //依次放置皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前皇后 n 放置到 n-1行的第一列，i=0为第一列
            array[n] = i;
            //判断当放置第n个皇后到第i列时，是否冲突
            if (judge(n)){
                //如果不冲突，则放置下一个皇后，开始递归
                check(n+1);
            }
            //如果冲突，就把当前皇后 n继续放置到下一列
        }
    }





    //查看：当我们放置第n个皇后时，就去检测该皇后是够和前面已经摆放的皇后冲突
    private boolean judge(int n){
        for (int i = 0; i < n; i++) {
            //array[i] == array[n] 表示这一个皇后和上一个皇后在同一列
            //Math.abs(n-1) == Math.abs(array[n] - array[i]) 表示这一个皇后和上一个皇后在同一条斜线上，等腰三角形
            if (array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i])){
                return false;
            }
        }
        return true;
    }



    //输出皇后摆放的位置
    private void printQueen(){
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }











}
